package weekthree;

import java.util.ArrayList;
import java.util.List;

public class RedundantConnection_684 {
    public int[] findRedundantConnection(int[][] edges) {
        edgesList = new ArrayList<>();
        int n = 0;
        //计算1-N的N
        for (int[] edge : edges) {
            n = Math.max(n, edge[1]);
        }
        visit = new boolean[n+1];
        for (int i = 0; i <= n; i++) {
            edgesList.add(new ArrayList<Integer>());
        }
        hasCycle = false;
        //dfs
        for (int[] edge : edges) {
            addEdge(edge[0], edge[1]);
            addEdge(edge[1], edge[0]);
            for (int i = 0; i <= n; i++) {
                visit[i] = false;
            }
            dfs(edge[0], -1);
            if (hasCycle) return edge;
        }

        return null;
    }

    //dfs模板 TODO:背诵
    private void dfs(int x, int fa) {
        visit[x] = true;
        for (int y : edgesList.get(x)) {
            if (y == fa) continue;
            if (visit[y]) hasCycle = true;
            else dfs(y, x);
        }
    }

    private void addEdge(int x, int y) {
        edgesList.get(x).add(y);
    }

    private List<List<Integer>> edgesList;
    private boolean[] visit;
    private boolean hasCycle;

    public static void main(String[] args) {
        int[] ans = new RedundantConnection_684().findRedundantConnection(new int[][]{{1,2},{1,3},{2,3}});
        System.out.println(ans[0] + " " + ans[1]);
    }
}
